package Prac;

public class P12_4 {
    //根据中序后序遍历创建二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        revers(postorder);//把后序反转,就能从前往后找根,只不过找到的先是右根再是左根
        return buildTreeHelper(inorder,postorder,0,inorder.length-1);
    }
    int i;
    public TreeNode buildTreeHelper(int[] inorder,int[] postorder,int left,int right){
        if(left>right){
            return null;
        }
        if(inorder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        int pos = find(postorder[i],inorder);
        i++;
        root.right = buildTreeHelper(inorder,postorder,pos+1,right);
        root.left = buildTreeHelper(inorder,postorder,left,pos-1);
        return root;

    }

    public int find(int key,int[] postorder){
        for(int i = 0;i<postorder.length;i++){
            if(postorder[i]==key){
                return i;
            }
        }
        return -1;
    }

    public void revers(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

}
